package lanqiao.真题.第13届Java大学B组;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author 挚爱之夕
 * @version 1.0
 * @implSpec
 * 爱丽丝刚从一处地下迷宫中探险归来，你能根据她对于自已行动路径的回忆，帮她画出迷宫地图吗？
 * 迷宫地图是基于二维网格的。

 * 爱丽丝会告诉你一系列她在迷宫中的移动步骤，每个移动步骤可能是上下左右四个方向中的一种，
 * 表示爱丽丝往这个方向走了一格。你需要根据这些移动步骤给出一个迷宫地图，并满足以下条件：
 * 1、爱丽丝能在迷宫内的某个空地开始，顺利的走完她回忆的所有移动步骤。
 * 2、迷宫内不存在爱丽丝没有走过的空地。
 * 3、迷宫是封闭的，即可通过墙分隔迷宫内与迷宫外。任意方向的无穷远处视为迷宫外，
 * 所有不与迷宫外联通的空地都视为是迷宫内。（迷宫地图为四联通，即只有上下左右视为联通)
 * 4、在满足前面三点的前提下，迷宫的墙的数量要尽可能少。

 * 【输入格式】
 * 第一行一个正整数N,表示爱丽丝回忆的步骤数量。
 * 接下来一行N个英文字符，仅包含UDLR四种字符，分别表示上(Up)、下(Dowm)、左(Left)、右(Right)。

 * 【输出格式】
 * 请通过字符画的形式输出迷宫地图。迷宫地图可能包含许多行，用字符 * 表示墙，用 空格 表示非墙。
 * 你的输出需要保证以下条件：
 * 1、至少有一行第一个字符为 *。
 * 2、第一行至少有一个字符为 *。

 * 3、每一行的最后一个字符为 *。
 * 4、最后一行至少有一个字符为 *。

 * 【样例输入】
 * 17
 * UUUULLLLDDDDRRRRU

 * 【样例输出】
 *  *****
 * *     *
 * * *** *
 * * *** *
 * * *** *
 * *     *
 *  *****
 * 【评测用例规模与约定】
 * 对于所有数据，0<N≤100.
 * 思路：
 * 1.二维数组模拟，N最大为100，开300 * 300 从中间走
 * 2.   1标记走过 2表示墙 0表示没处理过 3表示迷宫外的空地
 * 3.将当前位置朝向的前方、左边、右边置为2（如果那个位置为0）
 * 4.有一个问题迷宫内的可能存在0，因为路径不连通。从四个边开始dfs将0相邻的都置为3。最后迷宫内的0都是墙
 * 5.需要记录最大最小的x、y，截取这个子图，输出
 * @since 2023 - 03 - 11 - 11:02
 */
public class H_记忆迷宫 {
}

class Main_H{
    //模拟数组，大小足够用了
    static int[][] arr = new int[300][300];
    //最后截取的地图
    static int[][] graph;
    //初始坐标
    static int x = 150, y = 150;
    /*
    不能这样
    static int minX = Integer.MAX_VALUE, maxX = Integer.MIN_VALUE;
    static int minY = Integer.MAX_VALUE, maxY = Integer.MIN_VALUE;
    写的是走后再记录minX maxX  minY maxY
    可能导致边界少了一行
     */
    //这些变量记录路径边界，最后需要截取地图
    static int minX = x, maxX = x;
    static int minY = y, maxY = y;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        String line = sc.next();
        //起始点
        //周围设为墙
        set2(x, y);

        for(int i = 0; i < n; i++){
            char c = line.charAt(i);
            if(c == 'U'){
                up();
            }else if(c == 'D'){
                down();
            }else if(c == 'L'){
                left();
            }else{
                right();
            }
            //记录边界
            minX = Math.min(minX, x);
            minY = Math.min(minY, y);
            maxX = Math.max(maxX, x);
            maxY = Math.max(maxY, y);
        }
        //边界：迷宫的墙的数量要尽可能少，所以外围有一层墙
        minX--;
        minY--;
        maxX++;
        maxY++;
        //截取地图
        int w = maxY - minY + 1;
        int h = maxX - minX + 1;
        graph = new int[h][w];
        for(int i = minX; i <= maxX; i++){
            for(int j = minY; j <= maxY; j++){
                graph[i - minX][j - minY] = arr[i][j];
            }
        }
        //标记迷宫外空地: 将边界0及其相邻都置为3 表示迷宫外的空地
        for(int i = 0; i < graph.length; i++){
            //左边界
            if(graph[i][0] == 0){
                dfs(i, 0);
            }
            //右边界
            if(graph[i][graph[0].length - 1] == 0){
                dfs(i, graph[0].length - 1);
            }
        }
        for(int j = 0; j < graph[0].length; j++){
            //上边界
            if(graph[0][j] == 0){
                dfs(0, j);
            }
            //下边界
            if(graph[graph.length - 1][j] == 0){
                dfs(graph.length - 1, j);
            }
        }
        printGraph(graph);
    }
    //四个方向
    static int[][] dirs = {
            {-1, 0}, {1, 0}, {0, -1}, {0, 1}
    };
    static void dfs(int x, int y){
        graph[x][y] = 3;
        for(int[] dir : dirs){
            int nx = x + dir[0];
            int ny = y + dir[1];
            if(nx >= 0 && nx < graph.length && ny >= 0 && ny < graph[0].length && graph[nx][ny] == 0){
                dfs(nx, ny);
            }
        }
    }
    static void printGraph(int[][] graph){
        for(int[] line : graph){
            for(int t : line){
                //1标记走过 2表示墙 0表示没处理过 3表示迷宫外的空地
                if(t == 2 || t == 0){
                    System.out.print("*");
                }else{  //1 3
                    System.out.print(" ");
                }
            }
            System.out.println();
        }
    }
    //只有没处理过，才设置为墙
    static void set(int x, int y){
        if(arr[x][y] == 0){
            arr[x][y] = 2;
        }
    }

    static void set2(int x, int y){
        //标记走过
        arr[x][y] = 1;
        //将四周不为0的设置为2
        set(x, y - 1);
        set(x, y + 1);
        set(x - 1, y);
        set(x + 1, y);
    }
    static void up(){
        x--;
        set2(x, y);
//        set(x, y - 1);
//        set(x, y + 1);
//        set(x - 1, y);
    }
    static void down(){
        x++;
        set2(x, y);
//        set(x, y - 1);
//        set(x, y + 1);
//        set(x + 1, y);
    }
    static void left(){
        y--;
        set2(x, y);
//        set(x, y - 1);
//        set(x - 1, y);
//        set(x + 1, y);
    }
    static void right(){
        y++;
        set2(x, y);
//        set(x, y + 1);
//        set(x - 1, y);
//        set(x + 1, y);
    }
}

class Main_H1 {
    //初始点100,100
    static int x = 150;
    static int y = 150;
    static int maxx = 151;
    static int minx = 149;
    static int maxy = 151;
    static int miny = 149;

    static char[][] table = new char[300][300];
    static char[][] retablemap;

    public static void main(String[] args) {
//        初始化大地图全为走过的
        int n = table.length;
        int m = table[0].length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                table[i][j]= ' ';
            }
        }

        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        String empty = sc.next();
        char[] chars = empty.toCharArray();
//        初始化第一步   真实走过标记为1   墙为*
        table[y][x] = '1';
        table[y+1][x] = '*';
        table[y-1][x] = '*';
        table[y][x+1] = '*';
        table[y][x-1] = '*';

//            x        table[miny][minx]       table[miny][maxx]
//          0->200          99                        101
//       y  |
//         200              101
//                     table[maxy][minx]       table[maxy][maxx]
        //遍历移动步骤画出路和路边的墙
        for (char asc : chars) {
            if (asc == 'U') {
                up();
            } else if (asc == 'L') {
                left();
            } else if (asc == 'D') {
                down();
            } else if (asc == 'R'){
                right();
            }
//            map();
        }
        //最大最小的x和y维护最小矩阵，取小矩阵
        retablemap = new char[maxy-miny+1][maxx-minx+1];
        remap();

        //取最小矩阵的行和列
        int retablemapn = retablemap.length;
        int retablemapm = retablemap[0].length;

        //感染地图外侧 能被矩阵边感染的一定是地图外侧，外侧标记为2，第一行最后一行感染
        for (int i = 0; i < retablemapm; i++) {
            if (retablemap[0][i] == ' '){
                infect(retablemap,0,i,retablemapn,retablemapm);
            }
            if (retablemap[retablemapn-1][i] == ' '){
                infect(retablemap,retablemapn-1,i,retablemapn,retablemapm);
            }
        }
        //第一列最后一列感染
        for (int i = 0; i < retablemapn; i++) {
            if (retablemap[i][0] == ' '){
                infect(retablemap,i,0,retablemapn,retablemapm);
            }
            if (retablemap[i][retablemapm-1] == ' '){
                infect(retablemap,i,retablemapm-1,retablemapn,retablemapm);
            }
        }


//        遍历二维数组，填充墙‘ ’改为*，路标记1改‘ ’，地图外侧标记2改为‘ ’
        for (int i = 0; i < retablemapn; i++) {
            for (int j = 0; j < retablemapm; j++) {
                if (retablemap[i][j] == '1') {
                    retablemap[i][j] = ' ';
                } else if (retablemap[i][j] == ' ') {
                    retablemap[i][j] = '*';
                } else if (retablemap[i][j] == '2') {
                    retablemap[i][j] = ' ';

                }
            }
        }
//        打印填充墙后的图
//        System.out.println("-----------------");
        for (int i = 0; i < retablemapn; i++) {
            for (int j = 0; j < retablemapm; j++) {
                System.out.print(retablemap[i][j]);
            }
            System.out.println();
        }
    }
    //感染算法
    public static void infect(char[][] m,int i,int j,int N,int M){
        if (i < 0 || i>=N || j<0 || j>=M ||m[i][j] != ' '){
            return;
        }
        m[i][j] = '2';
        infect(m,i+1,j,N,M);
        infect(m,i-1,j,N,M);
        infect(m,i,j+1,N,M);
        infect(m,i,j-1,N,M);

    }
    //大矩阵取小矩阵
    public static void remap(){
        for (int i = miny; i <= maxy; i++) {
            for (int j = minx; j <= maxx; j++) {
                retablemap[i-miny][j-minx] = table[i][j];
            }
        }
    }


    //上 (Up)、 下 (Down)、左 (Left)、右 (Right)。
    public static void  up(){
        y--;
        table[y][x] = '1';
        if (table[y-1][x] != '1'){
            table[y-1][x] = '*';
        }
        if (table[y][x-1] != '1'){
            table[y][x-1] = '*';
        }
        if (table[y][x+1] != '1'){
            table[y][x+1] = '*';
        }
        miny = Math.min(y-1,miny);
    }
    public static void down(){
        y++;
        table[y][x] = '1';
        if (table[y+1][x] != '1'){
            table[y+1][x] = '*';
        }
        if (table[y][x-1] != '1'){
            table[y][x-1] = '*';
        }
        if (table[y][x+1] != '1'){
            table[y][x+1] = '*';
        }
        maxy = Math.max(y+1,maxy);
    }
    public static void left(){
        x--;
        table[y][x] = '1';
        if (table[y+1][x] != '1'){
            table[y+1][x] = '*';
        }
        if (table[y-1][x] != '1'){
            table[y-1][x] = '*';
        }
        if (table[y][x-1] != '1'){
            table[y][x-1] = '*';
        }
        minx = Math.min(x-1,minx);
    }
    public static void right(){
        x++;
        table[y][x] = '1';
        if (table[y+1][x] != '1'){
            table[y+1][x] = '*';
        }
        if (table[y-1][x] != '1'){
            table[y-1][x] = '*';
        }
        if (table[y][x+1] != '1'){
            table[y][x+1] = '*';
        }
        maxx = Math.max(x+1,maxx);
    }
}